/**
 * 1.为了避免空间溢出：
 * 		#define int long long
 * 		signed main(){}
 * 	用double
 * 2.数组开大一点
 * 3.只有顺序容器支持访问下标，关联容器及其他容器只支持foreach
 */
/**
 * set
 * 键盘输入 5 个整数，将这些数据保存到set中，采用迭代器正向遍历set中的元素并输出。
 * 集合，用于存储唯一元素或允许重复的元素，支持快速查找。
 * 常用方法： insert , erase , find ,
 * lower_bound(k) 查找第一个大于或等于k的元素，返回指向该元素的迭代器。
 * upper_bound(k) 查找第一个大于k的元素，并返回指向该元素的迭代器。
 * 应用：查重、区间问题。
 */
// #include<bits/stdc++.h>//万能头文件
// using namespace std;//写了这个才能用cin和cout
// int main() {
//     set<int>set;
//     for (int i = 0; i < 5; i++)
//     {
//         int num = 0;
//         cin >> num;
//         set.insert(num);
//     }
//     //set自动将数据从大到小排序
//     for (auto iter = set.begin(); iter != set.end(); iter++)
//         cout<< *iter << " ";
//	   //或
//     for(int c : st){
// 		   cout << c << " ";
//     }
//     return 0;
// }

/**
 * 从键盘获取一串字符串，要求去除重复的字符，请使用 set 解决。
 */
// #include <iostream>
// #include <set>
// using namespace std;

// int main() {

// 	char str[100] = { 0 };
// 	cin.getline(str, sizeof(str));
//     set<char> s;
//     for(int i = 0; str[i] != '\0'; i++) //遍历字符串
//         s.insert(str[i]); //将字符加入到set中
//     for(auto iter = s.begin(); iter != s.end(); iter++) //遍历set输出字符
//         cout << *iter << " ";
// 	return 0;
// }

/**
 * 给出一个大小为n的数组a，有m次询问，每次询问给出一个x，你需要输出数组a中大于x的最小值，如果不存在，输出-1。要求使用set实现。
 * 第一行两个整数n,m。
 * 第二行n个整数表示数组a。
 * 接下来m行，每行一个整数x。
 */
// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int n,m,x;
//     cin >> n >> m;
//     set<int> a;
//     for (int i = 0; i < n; i++)
//     {
//         cin >> x;
//         a.insert(num);
//     }
//     for (int i = 0; i < m; i++)
//     {
//         cin >> x;
//         auto iter = a.supper_bound(num);
//     }
// }

/**
 * 键盘输入 5 个整数，将这些数据保存到 vector 容器中，采用正向迭代器和反向迭代器分别遍历 vector 中的元素并输出。
 * vector ：动态数组，支持随机访问，常用于需要频繁增删操作的场景。
 * 常用方法：push_back  在容器尾部添加一个元素
 *          pop_back , resize , clear , emplace_back
 */
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
//     vector<int>v;
//     for (int i = 0; i < 5; i++)
//     {
//         int num = 0;
//         cin >> num;
//         v.push_back(num);
//     }
//     vector<int>::iterator iter1;
//     for (iter1 = v.begin(); iter1 != v.end(); iter1++)
//     {
//         cout << *iter1 << " ";
//     }
//     vector<int>::reverse_iterator iter2;
//     for (iter2 = v.rbegin(); iter2 != v.rend(); iter2++)
//     {
//         cout << *iter2 << " ";
//     }
//     return 0;
// }

/**
 * 给出一个包含n个整数的数组a,使用vector实现倒序输出数组的最后k个元素。
 */
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// 	int n,k;
// 	cin >> n >> k;
// 	vector<int>a;
// 	for (int i = 0; i < n; ++i)
// 	{
// 		int num;
// 		cin >> num;
// 		a.push_back(num);
// 	}
// 	for (auto it = a.rbegin(); it != a.rbegin() + k; ++it)
// 	{
// 		cout << *it << " ";
// 	}
// 	return 0;
// }

/**
 * 键盘输入 5 个整数，使用 vector 进行存储，使用 STL 排序算法对元素进行排序（从大到小），再使用 STL 遍历算法输出元素。（元素和元素之间使用空格隔开）
 */
// #include <iostream>
// #include <vector>
// #include <algorithm>
// using namespace std;

// void print(int x){ //打印x的变量
//     cout << x << " ";
// }
// int main() {
// 	int num;
// 	vector<int> v;
// 	for (int i = 0; i < 5; i++) { //输入
// 		cin >> num;
// 		v.push_back(num);
// 	}
//     sort(v.begin(), v.end(), greater<int>()); //从大到小排序
//     for_each(v.begin(), v.end(), print); //取出每个元素送入print函数中
// 	return 0;
// }

/**
 * 出一个包含n个整数的数组a,使用vector存储。用STL算法实现输出数组的第k大数。
 */
// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int n, k;
//     vector<int> a;
//     int num;
//     cin >> n >> k;
//     for (int i = 0; i < n; i++)
//     {
//         cin >> num;
//         a.push_back(num);
//     }
//     sort(a.begin(), a.end());
//     cout << a.at(k - 1) << endl;
//     return 0;
// }

/**
 * 请设计一个排队程序，用户有普通客人和 VIP 客人之分，VIP 客人不排队（即 VIP 客人在队列头部），请将已有的guest1和guest2放入队列中（guest1排在guest2前），并将VIP客人新增至队列头部。
 */
// #include <iostream>
// #include <deque>
// using namespace std;
// class Guest {
// public:
//     string name;
//     bool vip
//     Guest(string name, bool vip) {
//         this->name = name;
//         this->vip = vip;
//     }
// };
// int main() {
//     Guest guest1("张三", false);
//     Guest guest2("李四", false);
//     Guest vipGuest("王五", true);
//     deque<Guest> deque;

//     // write your code here......
//     deque.push_back(guest1);
//     deque.push_back(guest2);
//     //将vipGuest从队头入队
//     deque.push_front(vipGuest);
//     for (Guest g : deque) {
//         cout << g.name << " ";
//     }
//     return 0;
// }

/**
 * CPP50 统计字符串中各字母字符对应的个数
 * 键盘输入一个字符串，统计字符串中各个字母字符的个数。例如：键盘输入"Hello World!"，
 * 上述字符串中各个字母字符的出现的次数为： H:1 e:1 l:3 o:2 W:1 r:1 d:1 要求使用map实现，键的排序使用map默认排序即可。
 * 输入描述:键盘输入任意一个字符串
 * 输出描述:输出字母字符和字符对应的出现字数（注：相同字母的大小写算两个不同字符，字母字符和出现次数之间用:隔开，按 map 的默认顺序输出即可）
 * 示例1
 *    输入:Hello World
 *    输出:H:1W:1d:1e:1l:3o:2r:1
 * 题目所给的代码中，输入的字符串是一个字符数组，采用getline函数输入，这样会在输入的末尾增加一个'\0'表示字符串的结束，
 * 如果长度小于数组长度，输入所有字符后加'\0'，如果长度大于数组长度，截断输入的前面部分再在最后加'\0'。
 * 因此我们遍历字符数组第一个字符到最后的'\0'。要统计字符串中各个字母字符出现的次数，我们自然要遍历哈希表，
 * 对于每个字符我们用isalpha()函数检查是否是字母，如果是字母我们再用哈希表计数。哈希表中记录有两个值，
 * key值唯一标识这个东西，在这里就是我们的每个字母字符，value记录与这个key相关的数量，这里就是该字符出现的次数。
 * 全部字符遍历加入到哈希表中以后，我们遍历哈希表输出即可，哈希表依赖于红黑树会对key值按从小到大排序。
 */
// #include <iostream>
// #include <map>
// using namespace std;
// int main()
// {
//     char str[100] = {0};
//     cin.getline(str, sizeof(str));
//     map<char, int> mp;
//     for (int i = 0; str[i] != '\0'; i++)
//     {                        // 遍历字符串
//         if (isalpha(str[i])) // 对于是字母的字符
//             mp[str[i]]++;    // 加入哈希表，并统计次数
//     }
//     for (auto iter = mp.begin(); iter != mp.end(); iter++)  // 遍历哈希表
//         cout << iter->first << ":" << iter->second << endl; // 输出key与value
//     return 0;
// }

/**
 * 给出一个大小为n的数组a，有m次询问，每次询问给出一个x，你需要判断x是否在数组a中出现，如果出现了，输出"yes",否则输出"no"。要求使用map实现。
 */
// #include <bits/stdc++.h>
// using namespace std;
// int main()
// {
//     int n, m;
//     cin >> n >> m;
//     set<int> s;
//     int num = 0;
//     for (int i = 0; i < n; i++)
//     {
//         cin >> num;
//         s.insert(num);
//     }
//     while (m--)
//     {
//         cin >> num;
//         if (s.count(num))
//             cout << "yes" << endl;
//         else
//             cout << "no" << endl;
//     }
//     return 0;
// }

/**
 * STL算法：左闭右开---[begin,end)
 * 排序：sort(begin,end,cmp)支持自定义cmp，时间复杂度O(nlogn)
 * binary_search(begin,end,value)
 * 
 */
